package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         365,
		Discription: "水壶问题",
		Level:       2,
		Labels: map[string]int{
			"记忆化搜索": 1,
		},
	})
}

func CanMeasureWater(x int, y int, target int) bool {
	stateMap := make(map[[2]int]bool, 0)
	var dfs func(int, int) bool
	dfs = func(a, b int) bool {
		if res, exist := stateMap[[2]int{a, b}]; exist {
			return res
		}

		//注意要先把当前状态置为false，防止后边循环回来
		stateMap[[2]int{a, b}] = false

		//加起来也算
		if a == target || b == target || a+b == target {
			stateMap[[2]int{a, b}] = true
			return true
		}

		if dfs(0, b) || dfs(a, 0) || dfs(x, b) || dfs(a, y) || dfs(min(x, a+b), max(0, b-x+a)) || dfs(max(0, a-y+b), min(y, a+b)) {
			stateMap[[2]int{a, b}] = true
			return true
		}

		return false
	}

	return dfs(0, 0)
}